package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Scanner;

/*
有n个重量和价值分别为wi，vi的物品，从这些物品中挑选出总重量不超过W的物品，求所有挑选方案中价值总和的最大值。
    1 ≤ n ≤ 100
    1 ≤ wi ≤ 100
    1 ≤ vi ≤ 100 
    1 ≤ W ≤ 10000

输入：
    n=4
    (w,v)={(2,3),(1,2),(3,4),(2,2)}
    W=5

输出：
    7（选择第0，1，3号物品）

因为对每个物品只有选和不选两种情况，所以这个问题称为01背包。

5
1 2 3 4 5
1 4 3 4 1
10

12
 */
public class e背包问题byDPplus01背包 {
	public static void main(String[] args) {
		e背包问题byDPplus01背包 test = new e背包问题byDPplus01背包();
		test.useDynamicProgramming();
	}
	
	/**
	 * 前置方法
	 * 无需对weight[]排序
	 * 无需打包
	 */
	public void useDynamicProgramming() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] weight = new int[N];
		int[] value = new int[N];
		for (int i = 0; i < N; i++) {
			weight[i] = scanner.nextInt();
		}
		for (int i = 0; i < N; i++) {
			value[i] = scanner.nextInt();
		}
		int maxWeight = scanner.nextInt();
		/*
		int[N][maxWeight + 1]
		算上“还可继续装0重量的物体”，
		袋子可以“继续装物体”的可能种类是maxWeight + 1种
		所以N行，maxWeight + 1列
		列从0开始，逐渐+1直到maxWeight
		 */
		int[][] dp = new int[N][maxWeight + 1];
		int res = DynamicProgramming(weight, value, dp, N, maxWeight);
		System.out.println(res);
	}
	
	/**
	 * O(N^2)
	不用对weight[]排序
	dp表中每一格子，都存的是当前最大承重col在当前可选物品范围row内的可获得的最大价值
	先算小范围，一步一步推出最终结果
	 * @param weight
	 * @param value
	 * @param dp
	 * @param N
	 * @param maxWeight
	 * @return
	 */
	public int DynamicProgramming(int[] weight, int[] value, int[][] dp, int N, int maxWeight) {
		//初始化dp表第一行，col初始=0
		for (int col = 0; col < maxWeight + 1; col++) {
			//这个判断是辨别当前承重(也就是col)能不能装当前物体weight[0]
			if (weight[0] <= col) {//因为考虑到第一列是“还可继续装0重量的物体”；
				dp[0][col] = value[0];//能装则把weight[col]物体的价值存入表
			} else {
				dp[0][col] = 0;//不能装则装不了呗，就是0价值
			}
		}
		//开始遍历并填入其它行的数据
		for (int row = 1; row < N; row++) {//从第2行开始
			for (int col = 0; col < maxWeight + 1; col++) {//从第0列开始
				if (weight[row] <= col) {//当前承重(也就是col)能不能装当前物体weight[row]
					//能装
					int valueSelect = value[row] + dp[row - 1][col - weight[row]];//weight[row]物体的价值：value[row]  +  “剩下的承重(即col - weight[row])在剩下的范围(即row - 1)能获得的最大价值”：dp[row - 1][col - weight[row]]
					//不能装
					int valueNoSelect = dp[row - 1][col];//那就是“剩下的承重(即col - 0 = col)在剩下的范围(即row - 1)能获得的最大价值”：dp[row - 1][col]呗
					dp[row][col] = Math.max(valueSelect, valueNoSelect);//谁大就存谁
				} else {
					//当前承重不能装当前物体
					dp[row][col] = dp[row - 1][col];//那就是“剩下的承重(即col - 0 = col)在剩下的范围(即row - 1)能获得的最大价值”：dp[row - 1][col]呗
				}
			}
		}
		return dp[N - 1][maxWeight];//表中的右下角格子，就是我们要的结果
	}
}
